The subject matter disclosed herein relates to memory, and more particularly to the use of a memory circuit to compare input data against stored data using a blocking state.
Many different types of memory circuits can be used to compare input data (e.g., an input pattern or search data) against stored data (e.g., reference pattern(s) or a table of stored data). One example of such a memory circuit is Content Addressable Memory (CAM). When a CAM determines a match between the input data and the stored data, it returns the address(es) of the matching data. CAMs, which can perform the comparison between the input data and all of its stored data in a single clock cycle, can be used in a variety of applications requiring high speeds, including packet classification and packet forwarding in network routers.
One type of CAM, known as a Binary CAM (BCAM), uses binary data consisting entirely of two states (0s and 1s) for comparing input data to stored data as shown in the exemplary BCAM truth table of FIG. 1A. The BCAM truth table (FIG. 1A) is of an XOR gate (Exclusive OR), wherein the output is “yes” for a match only if both the input state and the stored state are the same. Conversely, the output is a “no” for a mismatch if the input state does not match the stored state.
A Ternary CAM (TCAM) uses data consisting of 0s and 1s as well as a third state known as a “no care” state (or “BX” state) as shown in the exemplary TCAM truth table of FIG. 1B. The TCAM truth table (FIG. 1B) is also of an XOR gate (Exclusive OR), wherein the output is “yes” for a match only if (a) the input state and the stored state are the same, (b) the stored state is a “no care” state (BX) regardless of the input state (0, 1, or BX), or (c) the input state is a “no care” state (BX) regardless of the stored state (0, 1, or BX). Conversely, the output is a “no” for a mismatch if the input state does not match the stored state, except in the case where the input state or the stored state is a “no care” state (BX). In many cases, the input data is a stream of several bits, where each input bit must be compared to a stored bit in a CAM cell to determine if all of the bits match to provide a “yes” output.
Most CAMs are built with static random access memory (SRAM) cells, where a typical CAM consists of two SRAM cells. In the past, a few 2/4T (2 transistors) Flash Negative-AND (NAND) based architectures have been employed for CAMs (e.g., U.S. Pat. Nos. 6,317,349, 7,110,275, 8,634,247). Recently, the concept of a 4T (four transistors) cell was also presented (e.g., U.S. Patent Application Publication No. 2014/0185349 A1). BCAMs and TCAMs have also been reported to be used for searches and, in cryptography, to safely compare input authentication patterns with reference patterns stored in the CAM (e.g., U.S. Pat. Nos. 8,780,633, 8,817,541, 8,717,794, and U.S. Patent Application Publication No. 2012/0143554).
The discussion above is merely provided for general background information and is not intended to be used as an aid in determining the scope of the claimed subject matter.